package LC;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/
 * Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
 */
public class LC_108_ConvertSortedArraytoBinarySearchTree_BinaryTree_BST_Recur_BinarySearch {
    public static void main(String[] args) {
        int[] a = {0, 1, 2, 3, 4, 5, 6};
        TreeNode root = Solution.sortedArrayToBST(a);
        List<List<Integer>> lists = levelOrder(root);
        System.out.println(lists);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null)
            return resultList;
        List<Integer> levelStorage = new LinkedList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(null);
        while (queue.size() > 1) {
            TreeNode top = queue.poll();
            if (top == null) {
                resultList.add(levelStorage);
                queue.offer(null);
                levelStorage = new LinkedList<>();
            } else {
                levelStorage.add(top.val);
                if (top.left != null)
                    queue.offer(top.left);
                if (top.right != null)
                    queue.offer(top.right);
            }
        }
        resultList.add(levelStorage);
        return resultList;
    }

    static class Solution {
        static TreeNode sortedArrayToBST(int[] nums) {
            int low = 0;
            int high = nums.length - 1;
            return sortedArrayToBST(nums, low, high);
        }

        private static TreeNode sortedArrayToBST(int[] nums, int low, int high) {
            TreeNode root = null;
            if (low <= high) {
                int mid = (low + high) / 2;
                root = new TreeNode(nums[mid]);
                root.left = sortedArrayToBST(nums, low, mid - 1);
                root.right = sortedArrayToBST(nums, mid + 1, high);
            }
            return root;
        }
    }
}